/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASI30/FONT#2=BASB30/FONT#10=BAXM30/FONT#11=ZERO30/FONT#3=STA200/FONT#4=NGB25
␈↓ ↓H␈↓␈↓βS␈↓∧ Department of Computer Science, STANFORD UNIVERSITY, Stanford, California 94305

␈↓ ↓H␈↓∧Telephone 415 497-4430␈↓ 
⊃April 14, 1983 




␈↓ ↓H␈↓Prof. Judea Pearl
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓UCLA
␈↓ ↓H␈↓Los Angeles, CA 90024

␈↓ ↓H␈↓Dear Judea:

␈↓ ↓H␈↓        Thanks␈α
for␈α∞the␈α
chapters␈α∞of␈α
your␈α∞book␈α
analyzing␈α∞α-β␈α
with␈α∞"informed␈α
ordering".␈α∞ I␈α
haven't
␈↓ ↓H␈↓read them yet.

␈↓ ↓H␈↓        So␈α
far␈α
as␈α
I␈α
know,␈α
1956␈α
was␈α
the␈α≡rst␈α
time␈α
anyone␈α
thought␈α
of␈α
α-β.␈α
 The␈α
Russians␈α
thought␈αof␈α
it
␈↓ ↓H␈↓independently␈αand␈αpublished␈αin␈α1963.␈α I␈αdon't␈αremember␈αwhat␈αKnuth␈αpublished␈αso␈αI'll␈αstart␈αover.
␈↓ ↓H␈↓There is no record of the Dartmouth discussions.

␈↓ ↓H␈↓        My␈α⊃idea␈α⊃mixed␈α∩the␈α⊃α-β␈α⊃idea␈α∩with␈α⊃that␈α⊃of␈α∩using␈α⊃optimistic␈α⊃and␈α∩pessimistic␈α⊃evaluations.
␈↓ ↓H␈↓Therefore,␈α⊂while␈α⊂I␈α⊂knew␈α⊂that␈α⊂α-β␈α⊂avoided␈α⊂some␈α⊂absolutely␈α⊂unnecessary␈α⊂computations,␈α⊂it␈α∂didn't
␈↓ ↓H␈↓occur␈αto␈αme␈αthat␈αthe␈αsimple␈αα-β␈αcould␈αbe␈αproved␈αto␈αgive␈αthe␈αsame␈αresult␈αas␈αminimax.␈α It␈αseems␈αto
␈↓ ↓H␈↓me␈α
that␈α
I␈α
learned␈α
about␈α
this␈α
from␈α
Tim␈α
Hart.␈α
 Roland␈α
Silver␈α
and␈α
Michael␈α
Levin␈α
may␈α
also␈αhave
␈↓ ↓H␈↓been involved.

␈↓ ↓H␈↓        I␈αalso␈αdidn't␈αknow␈αabout␈αKnuth's␈αweak␈α
and␈αstrong␈αforms␈αof␈αthe␈αalgorithm.␈α It␈αseems␈α
to␈αme
␈↓ ↓H␈↓that␈α⊂I␈α⊂always␈α⊂explained␈α⊂the␈α⊂strong␈α⊂form,␈α⊂but␈α∂the␈α⊂LISP␈α⊂program␈α⊂that␈α⊂I␈α⊂used␈α⊂to␈α⊂explain␈α⊂it␈α∂on
␈↓ ↓H␈↓blackboards had a bug so that it only did the weak form.


␈↓ ↓H␈↓Best regards,



␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Professor of Computer Science

␈↓ ↓H␈↓P.S.␈αI␈αdid␈αlook␈αat␈αsection␈α9.4,␈αand␈αI␈αhave␈αone␈αremark.␈α The␈αevaluation␈αfor␈αmove␈αordering␈αshould
␈↓ ↓H␈↓not␈α
be␈α
the␈α
same␈α
as␈α
the␈α
static␈α
evaluation␈α∞that␈α
would␈α
be␈α
used␈α
in␈α
choosing␈α
a␈α
move.␈α
 Firstly,␈α∞it␈α
can
␈↓ ↓H␈↓a≥ord␈α
to␈αbe␈α
more␈αadventurous␈α
including␈α
queen␈αsacri≡ces,␈α
etc.␈α Considerations␈α
include␈αthe␈α
expected
␈↓ ↓H␈↓time␈αto␈αevaluate␈α
it␈α(Most␈αqueen␈α
sacri≡ces␈αare␈αquickly␈αseen␈α
to␈αbe␈αbad.)␈α
and␈αan␈αaspiration␈αlevel.␈α
 We
␈↓ ↓H␈↓look␈α∞≡rst␈α∞at␈α∞moves␈α∞that␈α∞have␈α∞some␈α∂chance␈α∞of␈α∞reaching␈α∞an␈α∞aspiration␈α∞level.␈α∞ I␈α∞have␈α∂some␈α∞doubt
␈↓ ↓H␈↓about␈α∂your␈α∂results␈α∂that␈α∂the␈α⊂functions␈α∂are␈α∂∨at␈α∂near␈α∂good␈α⊂orderings.␈α∂ Of␈α∂course,␈α∂the␈α∂key␈α⊂item␈α∂is
␈↓ ↓H␈↓getting␈α
the␈α
an␈α
adequate␈α
move␈α
≡rst.␈α
 If␈α
this␈α
is␈α
accomplished,␈α
it␈α
doesn't␈α
matter␈α
how␈α
the␈α
others␈αare
␈↓ ↓H␈↓ordered.␈α∞ I␈α∞wish␈α∞I␈α∞had␈α∞time␈α∞to␈α∞go␈α∞through␈α∞your␈α∞mathematics␈α∞and␈α∞compare␈α∞it␈α∞with␈α∂my␈α∞intuitive
␈↓ ↓H␈↓ideas.
␈↓ ↓H␈↓αProf. Judea Pearl␈↓ ¬mApril 14, 1983␈↓ 
nPage 2␈↓ 


␈↓ ↓H␈↓        Realistic␈α∂mathematical␈α⊂models␈α∂involving␈α⊂the␈α∂work␈α⊂expended␈α∂on␈α⊂ordering␈α∂the␈α⊂moves␈α∂and
␈↓ ↓H␈↓work␈α∩involved␈α∩in␈α⊃the␈α∩tree␈α∩search␈α∩itself␈α⊃seem␈α∩di≠cult␈α∩to␈α∩discover␈α⊃and␈α∩even␈α∩more␈α∩di≠cult␈α⊃to
␈↓ ↓H␈↓compute␈α⊂with.␈α⊂ It␈α⊂seems␈α⊃even␈α⊂harder␈α⊂than␈α⊂the␈α⊂"two␈α⊃arm␈α⊂bandit"␈α⊂problems␈α⊂the␈α⊃RAND␈α⊂people
␈↓ ↓H␈↓worked on starting in the 1950s.